package leetcode.offer;

import leetcode.base.TreeNode;

import java.util.HashMap;

/**
 * ClassName: Offer07_BuildTree
 * Description: leetcode-剑指offer 07 重建二叉树
 * date: 2021-11-15 22:28
 *
 * @author liyifan
 */
public class Offer07_BuildTree {

    private HashMap<Integer, Integer> rootIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0;i < inorder.length;i++) {
            rootIndex.put(inorder[i], i);
        }

        return recur(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode recur(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        int preRootIndex = preLeft;
        int inRootIndex = rootIndex.get(preorder[preRootIndex]);
        TreeNode root = new TreeNode(preorder[preRootIndex]);

        int left = inRootIndex - inLeft;
        root.left = recur(preorder, inorder, preLeft + 1, preLeft + left, inLeft, inRootIndex - 1);
        root.right = recur(preorder, inorder, preLeft + left + 1, preRight, inRootIndex + 1, inRight);
        return root;
    }

}
